package com.ycz.algorithm.utils.hash;

import java.util.ArrayList;
import java.util.List;

/**
 * @Description 哈希表的动态数组（列表）实现
 * @ClassName HashMapChaining
 * @Author yanchengzhi
 * @date 2024.12.04 20:19
 */
public class HashMapChaining {

    int size; // 键值对数量

    int capacity; // 哈希表的容量

    double loadThres; // 触发扩容的负载因子阈值

    int extendRatio; // 扩容倍数

    List<List<Pair>> buckets; // 桶数组

    // 初始化
    public HashMapChaining() {
        size = 0;
        capacity = 4;
        loadThres = 2.0 / 3.0;
        extendRatio = 2;
        buckets = new ArrayList<>(capacity);
        for (int i = 0; i < capacity; i++) {
            buckets.add(new ArrayList<>());
        }
    }

    /**
     * @description: 哈希函数
     * @author: yanchengzhi
     * @date: 2024/12/4 20:27
     * @param: [key] key
     * @return: int
     */
    public int hashFunction(int key) {
        return key % capacity;
    }

    /**
     * @description: 负载因子
     * @author: yanchengzhi
     * @date: 2024/12/4 20:28
     * @param: []
     * @return: double
     */
    public double loadFactor() {
        return (double) size / capacity;
    }

    /**
     * @description: 查询操作
     * @author: yanchengzhi
     * @date: 2024/12/4 20:29
     * @param: [key]
     * @return: java.lang.String
     */
    public String get(int key) {
        int index = hashFunction(key);
        List<Pair> bucket = buckets.get(index);
        // 遍历桶，若找到key，则返回对应的value值
        for (Pair pair : bucket) {
            if (pair.key == key) {
                return pair.val;
            }
        }
        return null; // 未找到key，返回null
    }

    /**
     * @description: 添加操作
     * @author: yanchengzhi
     * @date: 2024/12/4 20:38
     * @param: [key, val]
     * @return: void
     */
    public void put(int key, String val) {
        // 负载因子超过阈值时，扩容
        if (loadThres < loadFactor()) {
            extend();
        }
        // 遍历桶，若找到指定key，则更新key对应的value值
        int index = hashFunction(key);
        List<Pair> bucket = buckets.get(index);
        for (Pair pair : bucket) {
            if (pair.key == key) {
                pair.val = val;
                return;
            }
        }
        // 若不存在这样的key，则将键值对加到列表尾部
        Pair newPair = new Pair(key, val);
        bucket.add(newPair);
        size++; // 数量+1
    }

    /**
     * @description: 删除操作
     * @author: yanchengzhi
     * @date: 2024/12/4 20:46
     * @param: [key]
     * @return: void
     */
    public void remove(int key) {
        int index = hashFunction(key);
        List<Pair> bucket = buckets.get(key);
        for (Pair pair : bucket) {
            if (pair.key == key) {
                bucket.remove(pair);
                size--;
                break;
            }
        }
    }

    // 哈希表扩容
    private void extend() {
        // 备份原哈希表
        List<List<Pair>> tmpBuckets = buckets;
        // 初始化扩容后的哈希表
        capacity = capacity * extendRatio;
        buckets = new ArrayList<>(capacity);
        for (int i = 0; i < capacity; i++) {
            buckets.add(new ArrayList<>());
        }
        size = 0;
        // 将原哈希表的所有键值对移到新的哈希表
        for (List<Pair> bucket : tmpBuckets) {
            for (Pair pair : bucket) {
                put(pair.key, pair.val);
            }
        }
    }

    // 打印哈希表
    public void print() {
        for (List<Pair> bucket : buckets) {
            List<String> tmp = new ArrayList<>();
            for (Pair pair : bucket) {
                tmp.add(pair.key + "==>" + pair.val);
            }
            System.out.println(tmp);
        }
    }

    public static void main(String[] args) {
        HashMapChaining hashMapChaining = new HashMapChaining();
        hashMapChaining.put(1, "a");
        hashMapChaining.put(2, "b");
        hashMapChaining.put(3, "c");
        hashMapChaining.print();
        System.out.println("----------------------------");
        hashMapChaining.put(4, "d");
        hashMapChaining.put(5, "e");
        hashMapChaining.put(6, "f");
        hashMapChaining.print();
        System.out.println("----------------------------");
        hashMapChaining.remove(6);
        hashMapChaining.print();
        System.out.println("----------------------------");
        hashMapChaining.put(6, "f");
        hashMapChaining.put(7, "g");
        hashMapChaining.put(8, "h");
        hashMapChaining.put(9, "i");
        hashMapChaining.put(10, "j");
        hashMapChaining.print();
        System.out.println("key为8对应的值为：" + hashMapChaining.get(8));
        System.out.println("key为11对应的值为：" + hashMapChaining.get(11));
    }

}
